#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
char s[200020];
int nt[200020];
int ans[200020];
void getnt()
{
	nt[0] = -1;
	int i = 0;
	int t = -1;
	while(i<n)
	{
		if(t==-1||s[i]==s[t])
		{
			i++;
			t++;
			nt[i] = t;
		}
		else t = nt[t];
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int sum = 0;
		scanf("%d",&n);
		scanf("%s",s);
		getnt();
		for(int i = 1;i<=n;i++)
		{
			ans[i] = ans[nt[i]]+1;
			sum = (sum+ans[i])%10007;
		}
		printf("%d\n",sum);
	}
}
